object VectorExample {
	def main() : Unit = { 
		println((new Vector()).realMain());
	}
}
class Vector{

	var v: Int [ ];

	def realMain():String = {
		var i:Int;
		var trash:Int;

		v = new Int[10];
		
		v[0] = 8;
		v[1] = 2;
		v[2] = 4;
		v[3] = 9;
		v[4] = 5;
		v[5] = 7;
		v[6] = 1;
		v[7] = 10;
		v[8] = 6;
		v[9] = 3;
		
		println("Before Quicksort");
		i = 0;
		while ( i < 10){
			println(v[i]);
			i=i+1;
		}


		trash = this.quicksort(0,9);

		println("After Quicksort");
		i = 0;
		while ( i < 10){
			println(v[i]);
			i=i+1;
		}

		return "End";
	}

	def partition(first:Int,last:Int,piv:Int):Int = {
		var p:Int;
		var j:Int;
		var i:Int;
		var trash:Int;
	
		p=v[piv];
		trash=this.swap(piv,last);
	
		j=first;
		i=first;
		while ( i < last ){
			if (v[i] < p){
				trash = this.swap(i,j);
				j=j+1;
			}
		i=i+1;
		}
	
		trash = this.swap(j,last);
		return j;
	}

	def swap(a:Int,b:Int):Int ={
		var temp:Int;
		temp = v[a];
		v[a]=v[b];
		v[b]=temp;
		return 0;
	}

	def quicksort(first:Int,last:Int):Int ={
		var piv:Int;	
		var trash:Int;	
		
		if ( first < last ){
			piv = (first + last)/2;
			piv = this.partition( first, last, piv);
			trash = this.quicksort(first,piv);
			trash = this.quicksort(piv+1,last);		
		}
			
		return 0;
	}	  

}
